package com.mdnote.practice.devide_and_rule;

import java.util.*;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/16
 * @description N 皇后
 */
public class LeetCode51 {

    public static void main(String[] args) {
        LeetCode51 leetCode51 = new LeetCode51();
        List<List<String>> res = leetCode51.solveNQueens(8);
        System.out.println(res.get(0));
        System.out.println(res.get(1));
    }

    public List<List<String>> solveNQueens(int n) {

        int[] checkerboard = new int[n];
        // 回溯法
        List<List<String>> resList = new ArrayList<>();
        recursion(0, checkerboard, resList);
        return resList;
    }

    private void recursion(int queen, int[] checkerboard, List<List<String>> resList) {
        if (queen == checkerboard.length) {
            // 生成棋盘
            generate(checkerboard, resList);
            return;
        }

        for (int i = 0; i < checkerboard.length; i++) {
            checkerboard[queen] = i;
            // 判断是否合法
            if (judge(queen, checkerboard)) {
                recursion(queen + 1, checkerboard, resList);
            }
        }
    }

    private boolean judge(int queen, int[] checkerboard) {

        // 不能是同一列、同一斜线
        for (int i = 0; i < queen; i++) {
            if (checkerboard[i] == checkerboard[queen] || (queen - i) == (checkerboard[queen] - checkerboard[i]) || (queen - i) == (checkerboard[i] - checkerboard[queen])) {
                return false;
            }
        }
        return true;
    }

    private void generate(int[] checkerboard, List<List<String>> resList) {
        String[] res = new String[checkerboard.length];
        for (int i = 0; i < res.length; i++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < checkerboard.length; j++) {
                stringBuilder.append(i == checkerboard[j] ? 'Q' : '.');
            }
            res[i] = stringBuilder.toString();
        }
        resList.add(Arrays.asList(res));
    }
}
